package com.gxc.array;

import java.util.Arrays;

/**
 * 3128. 直角三角形
 * 给你一个二维 boolean 矩阵 grid 。
 *
 * 请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值 都 为 1 。
 * 注意：
 * 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻
 */
public class NumberOfRightTriangles {

    public static void main(String[] args) {
        System.out.println(handle(new int[][]{
                {0,1,0},{0,1,1},{0,1,0}
        }));

        System.out.println(handle(new int[][]{
                {1,0,0,0},{0,1,0,1},{1,0,0,0}
        }));

        System.out.println(handle(new int[][]{
                {1,0,1},{1,0,0},{1,0,0}
        }));
    }

    /**
     * 已当前点作为直角点，看是否能有直角三角形
     * 用数组row[] 表示 第 i 行有多个1
     * 用数组col[] 表示 第 i 列有多个1
     * @param grid
     * @return
     */
    public static long handle(int[][] grid) {
        long res = 0;

        int[] row = new int[grid.length];
        int[] col = new int[grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    row[i] = row[i] + 1;
                    col[j] = col[j] + 1;
                }
            }
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    res = res + (long) (row[i] - 1) * (col[j]-1);
                }
            }
        }

        return res;
    }

    class Solution {
        public long numberOfRightTriangles(int[][] grid) {
            int n = grid.length, m = grid[0].length;
            int[] col = new int[m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    col[j] += grid[i][j];
                }
            }
            long res = 0;
            for (int i = 0; i < n; i++) {
                //统计数组之和
                int row = Arrays.stream(grid[i]).sum();
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 1) {
                        res += (row - 1) * (col[j] - 1);
                    }
                }
            }
            return res;
        }
    }


}
